\documentclass{ctexart}
 \usepackage{graphicx} 
 \usepackage{listings}
 \usepackage{color}
 
 \pagestyle{headings}
 
\title{BSTSorting设计思路和测试说明}
\author{谢飞扬 \\ 信息与计算科学 3210104010}
\date{\today}

\definecolor{green}{rgb}{0,0.7,0}
\definecolor{blue}{rgb}{0,0,0.8}
\definecolor{gray}{rgb}{0.95,0.95,0.95}
\definecolor{red}{rgb}{0.6,0,0}

\lstset{
        language=C++,
	basicstyle=\small\ttfamily,	
		keywordstyle=\color{blue}, 
		commentstyle=\color{green},   
		stringstyle=\rmfamily\slshape\color{red}, 
	backgroundcolor=\color{gray},     % 代码块背景颜色
	frame=leftline,						% 代码框形状
	framerule=12pt,
	rulecolor=\color{gray},      % 代码框颜色
	numbers=left,				% 左侧显示行号往左靠, 还可以为right ，或none，即不加行号
		numberstyle=\footnotesize\itshape,	% 行号的样式
		firstnumber=1,
		stepnumber=1,                  	% 若设置为2，则显示行号为1,3,5
		numbersep=5pt,               	% 行号与代码之间的间距
	keepspaces=true, 					
	showtabs=false,                 	% 在字符串中显示制表符
	tabsize=2,                     		% 默认缩进2个字符
	captionpos=b,                   	% 将标题位置设置为底部
	flexiblecolumns=true, 			%
	breaklines=true,                	% 设置自动断行
	breakatwhitespace=false,        	% 设置自动中断是否只发生在空格处
	breakautoindent=true,			%
	breakindent=1em, 			%
	title=\lstname,				%
	xleftmargin=1em,  xrightmargin=0em,     % 设定listing左右的空白
	aboveskip=1ex, belowskip=1ex,
	framextopmargin=0.5pt, framexbottommargin=0.5pt,
        abovecaptionskip=-2pt,belowcaptionskip=3pt,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false, columns=flexible, mathescape=true,
	texcl=true,
        fontadjust
}

\begin{document}
\maketitle
\section{项目设计思路}
设计了两个函数，一个类内函数outarray，用于返回排好序的数组，一个外部函数BSTSorting，对输入的数组用二叉搜索树排序，都加入了必要的const和\&。outarray仿照课本，通过private下的函数将root传递给public下的同名函数，从而通过中序遍历二叉搜索树，将排序后的数组输出。BSTSorting，当\_mode = 0时, 不乱序数组；当\_mode = 1时, 使用洗牌算法对数组\_arr乱序，之后开始计时用于测试排序执行时间，通过迭代器遍历和BinarySearchTree类内函数insert的调用，实现数组的排序，再调用outarray返回排序数组（从小到大排列）。下面是省去注释的函数代码。
\begin{lstlisting}
public:
    vector<Comparable> outarray()
	{
	    vector<Comparable>  _arr;
	    outarray(_arr,root);
	    return _arr;
	}
private:
    void outarray(vector<Comparable> & _arr,BinaryNode const *treenode)const;

template<typename Comparable>
void BinarySearchTree<Comparable>::outarray(vector<Comparable> & arr,BinaryNode const *treenode)const
{
    if(treenode!=nullptr)
    {
        outarray(arr,treenode->left);
	arr.push_back(treenode->element);
	outarray(arr,treenode->right);
    }
    return;
}
\end{lstlisting}
\begin{lstlisting}
template <typename Comparable>
void BSTSorting(vector<Comparable> & _arr, int _mode = 0)
{
    srand((unsigned int)time(nullptr));
    if(_mode!=0 && _mode!=1)
    {
	throw IllegalArgumentException{};
    }
    if(_mode==1)
    {
        for(int i=_arr.size()-1;i>0;i--)
        {
 	    int index = (int)(rand()%i);
 	    Comparable temp = _arr[index];
 	    _arr[index]=_arr[i];
	    _arr[i]=temp;
        }
    }
    clock_t start,end;
    start=clock();
    BinarySearchTree<Comparable> t;
    for(typename vector<Comparable>::iterator itr=_arr.begin();itr!=_arr.end();++itr)
    {
	t.insert(*itr);
    }
    _arr=t.outarray();
    end=clock();
    cout<<"the sorting spent "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<endl;
    return;
}
\end{lstlisting}

\section{测试说明}
main函数中创建了100000大小的数组分别测试\_mode = 0的最坏效率和\_mode = 1时的平均效率。
\begin{lstlisting}
int main(int argc,char*argv[])
{
    vector<int> arr;
    for(int i=0;i<100000;++i)
    {
	arr.push_back(i);
    }
    cout<<"顺序插入"<<endl;
    BSTSorting(arr);
    cout<<"乱序插入"<<endl;
    BSTSorting(arr,1);
    return 0;
\end{lstlisting}

\newpage
run.sh脚本文件输出的测试结果（run调用make及make report生成），及内存泄露检查如下。
\begin{figure}[htb]
  \center{\includegraphics[width=12cm]  {pic/run脚本.png}}
  \caption{\label{run}}
\end{figure}

\begin{figure}[htb]
  \centering{\includegraphics[width=12cm]  {pic/内存泄漏.png}}
  \caption{\label{valgrind}}
\end{figure}

\subsection{结论}
顺序插入时间在28s左右，乱序插入时间约为0.028s。显然顺序插入时，二叉搜索树不平衡，达到了最极端的情况即链表，此时深度是n，排序时间是$O(n^2)$。而随机打乱后的二叉搜索树比较平衡，其深度是$log_2(n)$排序时间为O(nlog(n))。

\end{document}
